package com.sicheng.datastruct.tree.基础图论.最小生成树;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/5 21:22
 */
public class Dijkstra {
    int n;
    int[][] g;  // 存储每条边
    int[] dist;  // 存储1号点到每个点的最短距离
    boolean[] st;   // 存储每个点的最短路是否已经确定

    //朴素方法
    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra() {
        dist[1] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j++)
                if (!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;

            // 用t更新其他点的距离
            for (int j = 1; j <= n; j++)
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);

            st[t] = true;
        }

        if (dist[n] == Integer.MAX_VALUE)
            return -1;
        return dist[n];
    }



}
